#include <stdio.h>
// 问题描述:
// 一只青蛙可以选择一次跳一个或两个台阶，请问青蛙跳上第n阶台阶一共有几种跳法？
// 示例:
// n=2 时，青蛙可以选择两种方法，一种是一级一级的跳，一种是一次跳两级  不防表示为:(1,1) (2) 共 2 种 跳法
// n=3 时，有 (1,1,1) (1,2) 其中，(1,1,1) 不能排列组合 而 (1,2) 可以有两种排列组合 即 (1,2) (2,1)  所以共 3 种跳法
// n=4 时，有 (1,1,1,1) (1,1,2) (2,2)  第二个有三种组合 因此共有 1+1+3 == 2+3 == 5 种跳法
// n=5 时，有 (1,1,1,1,1) (1,1,1,2) (1,2,2) 1+4+3 == 5+3 == 8 种跳法
// n=6 时，有 (1,1,1,1,1,1) (1,1,1,1,2) (1,1,2,2) (2,2,2) 1+5+4+3 == 5+8 == 13 种跳法

// n=n 时，有 (1,1,1,...,1)   (1,1,1,...,2)  (1,1,...,1,2,2)   (1,1,..,1,2,...,2)   ..........         (2,2,...,2) or (1,2,2,...,2)          
//              n个1 0个2     (n-2)个1 1个2   (n-4)个1 2个2     (n-8)个1 4个2       (n-2x)个1 x个2      0个1，n/2 个2 or 1个1，(n-1)/2个2
// 排列组合   C(n,0) 个组合    C(n-1,1)个组合  C(n-2,2)个组合    C(n-4,4)个组合      C(n-x,x)个组合       C(0,n)或 C(1,(n-1)/2)个组合
// 括号内第一个为组合的下标
//  因此 数学表达为： Σ -> sigma(0,n) 表示从 0 开始 到 n 结束 C(n-x,x)为表达式  n为常量 x为变量

// fac()阶乘函数
int fac(int x)
{
    int w = 1;
    int i = 1;
    if ( x == 0) return 1;
    else
    {
        for (i = 1;i <= x;i++) 
        w *= i;
    }
    return w;
}
// C() 排列组合函数
int C(int n,int x)
{
    int a = fac(n-x)*fac(x);
    int b = fac(n);
    return b/a ;
}
// total_jumps()
int total_jumps(int n)  // 跳上第n阶台阶的所有跳法
{
    int w = 0;
    int m = 0;
    for (w = 0; w<=n; w++)
    {
        m += C(n-w,w);

        int v = n-2*w;  // 防止计算负数的阶乘
        if (v < 0) break;
    }
    return m ;
}


int main()
{
    int a = fac(5);   // 测试fac函数的正确性
    printf("%d\n",a); // 120 正确

    int b = C(5,2);    // 测试C函数的正确性
    printf("%d\n",b);  // 10 正确

    int c = total_jumps(10); //测试最终结果
    printf("%d\n",c);  // 89 种 正确

    return 0;
}